﻿public class Solution {
    public int CountSubstrings(string s)
    {
        bool[,] dp = new bool[s.Length, s.Length];
        int res = 0;

        for (int i = s.Length - 1; i >= 0; i--)
        {
            for (int j = i; j < s.Length; j++)
            {
                if (j == i) dp[i, j] = true;
                else if (j - i == 1 && s[i] == s[j]) dp[i, j] = true;
                else if (s[i] == s[j]) dp[i, j] = dp[i + 1, j - 1];

                if (dp[i, j]) res++;
            }
        }

        return res;
    }

    public static void Main(string[] args)
    {
        string s = "aaa";
        Solution solution = new Solution();
        int res = solution.CountSubstrings(s);
        Console.WriteLine(res);
    }
}